Simultaneous Contact Representations of Planar Graphs
摘要
Contact representations of planar graphs by triangles or – in the bipartite case – by vertical and horizontal segments in the plane can be constructed in linear time. It is also known that in both of these cases, deciding whether a representation of an induced subgraph of an input graph can be extended into a representation of the entire graph is NP-hard. We complement these results by showing that simultaneous representation of two graphs is also NP-hard (both for triangle contact graphs, and for grid contact ones). We show this by a unified reduction via simultaneous contact representations of so-called x-y-stretchable sets of convex sets, which implies NP-hardness of the simultaneous representation problem for many more classes of geometric contact graphs.