Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time

Hong, Seok-Hee and Nagomachi, Hiroshi (2016) Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 321-334(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_25).

Full text not available from this repository.

Abstract

Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines 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 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1552

Actions (login required)

View Item View Item