%0 Journal Article %1 cfkkrw-sapsr-TCS22 %A Chaplick, Steven %A Felsner, Stefan %A Kindermann, Philipp %A Klawitter, Jonathan %A Rutter, Ignaz %A Wolff, Alexander %D 2022 %J Theoretical Computer Science %K %P 66--74 %R 10.1016/j.tcs.2022.03.031 %T Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations %V 919 %X A rectangular dual of a graph $G$ is a contact representation of $G$ by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. The simultaneous representation problem for rectangular duals asks whether two (or more) given graphs that share a subgraph admit rectangular duals that coincide on the shared subgraph. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. We describe linear-time algorithms for the partial representation extension problem and the simultaneous representation problem for rectangular duals when each input graph is given together with a REL. Both algorithms are based on formulations as linear programs, yet they have geometric interpretations and can be seen as extensions of the classic algorithm by Kant and He that computes a rectangular dual for a given graph.

@article{cfkkrw-sapsr-TCS22, abstract = {A rectangular dual of a graph $G$ is a contact representation of $G$ by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The \emph{partial representation extension problem} for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. The \emph{simultaneous representation problem} for rectangular duals asks whether two (or more) given graphs that share a subgraph admit rectangular duals that coincide on the shared subgraph. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. \par We describe linear-time algorithms for the partial representation extension problem and the simultaneous representation problem for rectangular duals when each input graph is given together with a REL. Both algorithms are based on formulations as linear programs, yet they have geometric interpretations and can be seen as extensions of the classic algorithm by Kant and He that computes a rectangular dual for a given graph.}, added-at = {2023-12-13T04:04:03.000+0100}, arxiv = {https://arxiv.org/abs/2102.02013}, author = {Chaplick, Steven and Felsner, Stefan and Kindermann, Philipp and Klawitter, Jonathan and Rutter, Ignaz and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/24fe971003b653241805aff62664646e0/admin}, doi = {10.1016/j.tcs.2022.03.031}, interhash = {9188fdb9786fcc4d50bb23849883f268}, intrahash = {4fe971003b653241805aff62664646e0}, journal = {Theoretical Computer Science}, keywords = {}, pages = {66--74}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/cfkkrw-sapsr-TCS22.pdf}, timestamp = {2023-12-13T04:04:03.000+0100}, title = {Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations}, video = {https://vimeo.com/541744478}, volume = 919, year = 2022 }