Unbent Collections of Orthogonal Drawings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910050948218880 |
|---|---|
| author | Antić, Todor Liotta, Giuseppe Masařík, Tomáš Ortali, Giacomo Pfretzschner, Matthias Stumpf, Peter Wolff, Alexander Zink, Johannes |
| author_facet | Antić, Todor Liotta, Giuseppe Masařík, Tomáš Ortali, Giacomo Pfretzschner, Matthias Stumpf, Peter Wolff, Alexander Zink, Johannes |
| contents | Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we apply this idea to orthogonal graph drawing. Due to the orthogonal drawing style, we focus on 4-graphs, that is, graphs of maximum degree 4. We restrict ourselves to plane graphs, that is, planar graphs whose embedding is fixed. Our goal is to represent any plane 4-graph $G$ by an unbent collection, that is, a collection of orthogonal drawings of $G$ that adhere to the embedding of $G$ and ensure that each edge of $G$ is drawn without bends in at least one of the drawings. We investigate two objectives. First, we consider minimizing the number of drawings in an unbent collection. We prove that every plane 4-graph can be represented by a collection with at most three drawings, which is tight. We also give necessary and sufficient conditions for a graph to admit an unbent collection of size $2$. Second, we consider minimizing the total number of bends over all drawings in an unbent collection. We show that this problem is NP-hard and give a 3-approximation algorithm. For the special case of plane triconnected cubic graphs, we show how to compute minimum-bend collections in linear time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_18390 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unbent Collections of Orthogonal Drawings Antić, Todor Liotta, Giuseppe Masařík, Tomáš Ortali, Giacomo Pfretzschner, Matthias Stumpf, Peter Wolff, Alexander Zink, Johannes Computational Geometry Discrete Mathematics Data Structures and Algorithms Combinatorics 68R10 Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we apply this idea to orthogonal graph drawing. Due to the orthogonal drawing style, we focus on 4-graphs, that is, graphs of maximum degree 4. We restrict ourselves to plane graphs, that is, planar graphs whose embedding is fixed. Our goal is to represent any plane 4-graph $G$ by an unbent collection, that is, a collection of orthogonal drawings of $G$ that adhere to the embedding of $G$ and ensure that each edge of $G$ is drawn without bends in at least one of the drawings. We investigate two objectives. First, we consider minimizing the number of drawings in an unbent collection. We prove that every plane 4-graph can be represented by a collection with at most three drawings, which is tight. We also give necessary and sufficient conditions for a graph to admit an unbent collection of size $2$. Second, we consider minimizing the total number of bends over all drawings in an unbent collection. We show that this problem is NP-hard and give a 3-approximation algorithm. For the special case of plane triconnected cubic graphs, we show how to compute minimum-bend collections in linear time. |
| title | Unbent Collections of Orthogonal Drawings |
| topic | Computational Geometry Discrete Mathematics Data Structures and Algorithms Combinatorics 68R10 |
| url | https://arxiv.org/abs/2502.18390 |