Let $$\mathcal {G} $$ be a plane triangulated graph. A rectangular dual of $$\mathcal {G} $$ is a partition of a rectangle R into a set $$\mathcal {R} $$ of interior-disjoint rectangles, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge. A rectangular dual is sliceable if it can be recursively subdivided along horizontal or vertical lines. A graph is rectangular if it has a rectangular dual and sliceable if it has a sliceable rectangular dual. There is a clear characterization of rectangular graphs. However, a full characterization of sliceable graphs is still lacking. The currently best result Yeap and Sarrafzadeh, 1995 proves that all rectangular graphs without a separating 4-cycle are sliceable. In this paper we introduce a recursively defined class of graphs and prove that these graphs are precisely the nonsliceable graphs with exactly one separating 4-cycle.
['Vincent Kusters', 'Bettina Speckmann']
Towards Characterizing Graphs with a Sliceable Rectangular Dual