Small-Area Orthogonal Drawings of 3-Connected Graphs

Biedl, Therese and Schmidt, Jens M. (2015) Small-Area Orthogonal Drawings of 3-Connected Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 153-165(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_13).

Full text not available from this repository.

Abstract

It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most (49/64)*n^2+O(n)≈0.76n^2. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to (9/16)*n^2+O(n)≈0.56n^2. The drawing uses the 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.280 Canonical Ordering
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.600 Poly-line > P.600.700 Orthogonal
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:14
Last Modified: 04 May 2016 16:14
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1485

Actions (login required)

View Item View Item