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:

Full text not available from this repository.


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

Actions (login required)

View Item View Item