Drawing planar graphs with few geometric primitives

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

doi:10.1007/978-3-319-68705-6_24

Drawing planar graphs with few geometric primitives

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

2 Downloads (Pure)

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 language	English
Title of host publication	43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
Subtitle of host publication	Revised Selected Papers
Editors	Gerhard J. Woeginger, Hans L. Bodlaender
Publisher	Springer
Pages	316-329
Number of pages	14
ISBN (Electronic)	978-3-319-68705-6
ISBN (Print)	978-3-319-68704-9
DOIs	https://doi.org/10.1007/978-3-319-68705-6_24
Publication status	Published - 2017
Event	43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017) - Kapellerput, Eindhoven, Netherlands Duration: 21 Jul 2017 → 23 Jul 2017 http://www.win.tue.nl/wg2017/

Publication series

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

Workshop

Workshop	43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)
Abbreviated title	WG 2017
Country/Territory	Netherlands
City	Eindhoven
Period	21/07/17 → 23/07/17
Internet address	http://www.win.tue.nl/wg2017/

Access to Document

10.1007/978-3-319-68705-6_24

https://arxiv.org/abs/1703.01691

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

Hültenschmidt, G. ; Kindermann, P. ; Meulemans, W. et al. / Drawing planar graphs with few geometric primitives. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG): Revised Selected Papers. editor / Gerhard J. Woeginger ; Hans L. Bodlaender. Springer, 2017. pp. 316-329 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d058b3b225d945e88b2f5bdc32b019c6,

title = "Drawing planar graphs with few geometric primitives",

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.",

author = "G. H{\"u}ltenschmidt and P. Kindermann and W. Meulemans and A. Schulz",

year = "2017",

doi = "10.1007/978-3-319-68705-6_24",

language = "English",

isbn = "978-3-319-68704-9",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "316--329",

editor = "Woeginger, {Gerhard J.} and Bodlaender, {Hans L.}",

booktitle = "43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)",

address = "Germany",

note = "43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), WG 2017 ; Conference date: 21-07-2017 Through 23-07-2017",

url = "http://www.win.tue.nl/wg2017/",

}

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

Drawing planar graphs with few geometric primitives. / Hültenschmidt, G.; Kindermann, P.; Meulemans, W. et al.
43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG): Revised Selected Papers. ed. / Gerhard J. Woeginger; Hans L. Bodlaender. Springer, 2017. p. 316-329 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10520 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Drawing planar graphs with few geometric primitives

AU - Hültenschmidt, G.

AU - Kindermann, P.

AU - Meulemans, W.

AU - Schulz, A.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85034081509&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-68705-6_24

DO - 10.1007/978-3-319-68705-6_24

M3 - Conference contribution

SN - 978-3-319-68704-9

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 316

EP - 329

BT - 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

A2 - Woeginger, Gerhard J.

A2 - Bodlaender, Hans L.

PB - Springer

T2 - 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)

Y2 - 21 July 2017 through 23 July 2017

ER -

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

Drawing planar graphs with few geometric primitives

Abstract

Publication series

Workshop

Access to Document

Other files and links

Fingerprint

Cite this