Reembedding a 1Plane Graph into a StraightLine Drawing in Linear TimeHong, SeokHee and Nagomachi, Hiroshi (2016) Reembedding a 1Plane Graph into a StraightLine Drawing in Linear Time. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 321334(Official URL: http://dx.doi.org/10.1007/9783319501062_25). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_25
AbstractThomassen characterized some 1plane embedding as the forbidden configuration such that a given 1plane embedding of a graph is drawable in straightlines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335–341, 1988]. In this paper, we characterize some 1plane embedding as the forbidden configuration such that a given 1plane embedding of a graph can be reembedded into a straightline drawable 1plane embedding of the same graph if and only if it does not contain the configuration. Reembedding of a 1plane embedding preserves the same set of pairs of crossing edges. We give a lineartime algorithm for finding a straightline drawable 1plane reembedding or the forbidden configuration.
Actions (login required)
