A characterization of terminal planar networks by forbidden structures

2026/03/17 by Haruki Miyaji, Yuki Noguchi, Hexuan Liu +4 · 1 voice
Mathematics · #math.CO

paper · pdf

Abstract

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.

Citations

• Planar Rooted Phylogenetic Networks
• Some new results on bar visibility of digraphs
• Upward planarity testing
• Algorithms for plane representations of acyclic digraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient Planarity Testing
• Über eine Eigenschaft der ebenen Komplexe
• Sur le problème des courbes gauches en Topologie

Discussions

• A characterization of terminal planar networks by forbidden structures https://arxiv.org/abs/2603.16657v1 [bsky, 0 points, 0 comments]

Related

• Planar Rooted Phylogenetic Networks
• Asymptotic Enumeration of Subclasses of Level-2 Phylogenetic Networks
• Planar unclustered graphs to model technological and biological networks
• Bounding the Size of a Network Defined By Visibility Property
• Mimicking Networks and Succinct Representations of Terminal Cuts