Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2603.16657 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915869980884992 |
|---|---|
| author | Miyaji, Haruki Noguchi, Yuki Liu, Hexuan Suzuki, Takatora Watanabe, Keita Wu, Taoyang Hayamizu, Momoko |
| author_facet | Miyaji, Haruki Noguchi, Yuki Liu, Hexuan Suzuki, Takatora Watanabe, Keita Wu, Taoyang Hayamizu, Momoko |
| contents | The class of terminal planar networks was recently introduced from a biological perspective in relation to the visualization of phylogenetic networks, and its connection to upward planar networks has been established. We provide a Kuratowski-type theorem that characterizes terminal planar networks by a finite set of forbidden structures, defined via six families of 0/1-labeled graphs. Another characterization based on planarity of supergraphs yields linear-time algorithms for testing terminal planarity and for computing such planar drawings. We describe an application that is potentially relevant in broader, non-phylogenetic settings. We also discuss a connection of our main result to an open problem on the forbidden structures of single-source upward planar networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_16657 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A characterization of terminal planar networks by forbidden structures Miyaji, Haruki Noguchi, Yuki Liu, Hexuan Suzuki, Takatora Watanabe, Keita Wu, Taoyang Hayamizu, Momoko Combinatorics 05C75, 05C10 The class of terminal planar networks was recently introduced from a biological perspective in relation to the visualization of phylogenetic networks, and its connection to upward planar networks has been established. We provide a Kuratowski-type theorem that characterizes terminal planar networks by a finite set of forbidden structures, defined via six families of 0/1-labeled graphs. Another characterization based on planarity of supergraphs yields linear-time algorithms for testing terminal planarity and for computing such planar drawings. We describe an application that is potentially relevant in broader, non-phylogenetic settings. We also discuss a connection of our main result to an open problem on the forbidden structures of single-source upward planar networks. |
| title | A characterization of terminal planar networks by forbidden structures |
| topic | Combinatorics 05C75, 05C10 |
| url | https://arxiv.org/abs/2603.16657 |