Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2016-002 (July 14, 2016)
Re-embedding a 1-Plane Graph into a Straight-line Drawing in Linear Time
by Seok-Hee Hong and Hiroshi Nagamochi
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
We give a linear-time algorithm for finding a
straight-line drawable 1-plane re-embedding or
the forbidden configuration.