Options
Small-area orthogonal drawings of 3-connected graphs
Publikationstyp
Conference Paper
Date Issued
2015-11-27
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
9411 LNCS
Start Page
153
End Page
165
Citation
International Symposium on Graph Drawing (GD 2015)
Publisher DOI
Scopus ID
Publisher
Springer
It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most 49/64 n2+O(n)≈0.76n2. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to9/16n2+O(n)≈0.56n2.Thedrawingusesthe 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.
DDC Class
510: Mathematik