Drawing Planar Cubic 3Connected Graphs with Few Segments: Algorithms and ExperimentsIgamberdiev, Alexander and Meulemans, Wouter and Schulz, André (2015) Drawing Planar Cubic 3Connected Graphs with Few Segments: Algorithms and Experiments. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 113124(Official URL: http://dx.doi.org/10.1007/9783319272610_10). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_10
AbstractA drawing of a graph can be understood as an arrangement of geometric objects. In the most natural setting the arrangement is formed by straightline segments. Every cubic planar 3connected graph with n vertices has such a drawing with only n/2 +3 segments, matching the lower bound. This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings. We introduce two new algorithms that also produce drawings with n/2+3 segments. One algorithm is based on a sequence of dual edge contractions, the other is based on a recursion of nested cycles. We also show a flaw in the algorithm of Mondal et al. and present a fix for it. We then compare the performance of these three algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings. We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution. However, the new algorithms perform better in terms of edge length and minimal face aspect ratio.
Actions (login required)
