%0 Conference Paper %1 hkms-dttfg-wg17 %A Hültenschmidt, Gregor %A Kindermann, Philipp %A Meulemans, Wouter %A Schulz, André %B Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17) %D 2017 %E Bodlaender, Hans L. %E Woeginger, Gerhard J. %I Springer-Verlag %K complexity myown visual %P 316--329 %R 10.1007/978-3-319-68705-6_24 %T Drawing Planar Graphs with Few Geometric Primitives %V 10520 %X We define the visual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). We show that trees can be drawn with $3n/4$ straight-line segments on a polynomial grid, and with $n/2$ straight-line segments on a quasi-polynomial grid. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only $(5n - 11)/3$ arcs. This provides a significant improvement over the lower bound of $2n$ for line segments for a nontrivial graph class.

@inproceedings{hkms-dttfg-wg17, abstract = {We define the visual complexity of a plane graph drawing to be the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g. you need only one line segment to draw two collinear edges of the same vertex). We show that trees can be drawn with $3n/4$ straight-line segments on a polynomial grid, and with $n/2$ straight-line segments on a quasi-polynomial grid. We also study the problem of drawing maximal triangulations with circular arcs and provide an algorithm to draw such graphs using only $(5n - 11)/3$ arcs. This provides a significant improvement over the lower bound of $2n$ for line segments for a nontrivial graph class.}, added-at = {2017-06-06T12:43:33.000+0200}, arxiv = {https://arxiv.org/abs/1703.01691}, author = {H{\"u}ltenschmidt, Gregor and Kindermann, Philipp and Meulemans, Wouter and Schulz, Andr{\'e}}, biburl = {https://www.bibsonomy.org/bibtex/2d78592028380c58800fa710b830c30f0/kindermann}, booktitle = {Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17)}, doi = {10.1007/978-3-319-68705-6_24}, editor = {Bodlaender, Hans L. and Woeginger, Gerhard J.}, interhash = {90d9798b6cbdf756e6121c1386f5853a}, intrahash = {d78592028380c58800fa710b830c30f0}, keywords = {complexity myown visual}, month = jun, pages = {316--329}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2017-wg-fewarcs.pdf}, timestamp = {2019-10-01T18:02:50.000+0200}, title = {Drawing Planar Graphs with Few Geometric Primitives}, volume = 10520, year = 2017 }