Drawing planar graphs with few geometric primitives

G. Hültenschmidt, P. Kindermann, W. Meulemans, A. Schulz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

We define the visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw two collinear edges of the same vertex). Let n denote the number of vertices of a graph. 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. Further, we present an algorithm for drawing planar 3-trees with (8n−17)/3
(8n−17)/3
segments on an O(n)×O(n 2 )
O(n)×O(n2)
grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n / 2 edges on an O(n)×O(n 2 )
O(n)×O(n2)
grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3
(5n−11)/3
arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.
Original languageEnglish
Title of host publication43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
Subtitle of host publicationRevised Selected Papers
EditorsGerhard J. Woeginger, Hans L. Bodlaender
PublisherSpringer
Pages316-329
Number of pages14
ISBN (Electronic)978-3-319-68705-6
ISBN (Print)978-3-319-68704-9
DOIs
Publication statusPublished - 2017
Event43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017) - Kapellerput, Eindhoven, Netherlands
Duration: 21 Jul 201723 Jul 2017
http://www.win.tue.nl/wg2017/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10520 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)
Abbreviated titleWG 2017
CountryNetherlands
CityEindhoven
Period21/07/1723/07/17
Internet address

Fingerprint Dive into the research topics of 'Drawing planar graphs with few geometric primitives'. Together they form a unique fingerprint.

  • Cite this

    Hültenschmidt, G., Kindermann, P., Meulemans, W., & Schulz, A. (2017). Drawing planar graphs with few geometric primitives. In G. J. Woeginger, & H. L. Bodlaender (Eds.), 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG): Revised Selected Papers (pp. 316-329). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10520 LNCS). Springer. https://doi.org/10.1007/978-3-319-68705-6_24