Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2016-003 (July 14, 2016)

Planarity of Graphs with Crossable Edges
by Seok-Hee Hong and Hiroshi Nagamochi

pdf File

Let $H=(V_H,E_H)$ be an undirected graph with a subset $E$ of the edge set $E_H$, where we call the edges in $E$ {\em red edges} and the edges in $E_H-E$ {\em blue edges}. An embedding of $H$ into the plane is called an {\em $E$-planar} embedding if no red edge crosses any other edges whereas two blue edges may cross. In this paper, we give a complete characterization of an instance $(H,E)$ that admits no $E$-planar embedding via forbidden subgraphs with red/blue edges. Furthermore we design a linear-time algorithm that finds either an $E$-planar embedding or a forbidden subgraph. The problem setting can enable us to formulate a problem of finding a planar embedding of a planar graph $G$ with an additional constraint such that, for specified sets $S_1,S_2,\ldots,S_k$ of vertices, all the vertices in each $S_i$ appear along the same facial cycle. To see this, we regard all edges in $G$ as red edges and add a star $s_i$ with blue edges $s_i t$, $t\in S_i$ for each $i$. For example, this allows us to find a planar embedding of a planar graph $G$ such that the rotation systems of some vertices are predetermined.