SmallArea Orthogonal Drawings of 3Connected GraphsBiedl, Therese and Schmidt, Jens M. (2015) SmallArea Orthogonal Drawings of 3Connected Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 153165(Official URL: http://dx.doi.org/10.1007/9783319272610_13). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_13
AbstractIt is wellknown 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 3connected, then the area can be reduced even further to (9/16)*n^2+O(n)≈0.56n^2. The drawing uses the 3canonical order for (not necessarily planar) 3connected 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. Actions (login required)
