|
|||||
|
|
A characterization of level planar graphs |
|
| Authors: | Patrick Healy Ago Kuusik Sebastian Leipert |
| Affiliation: | a Department of Computer Science and Information Systems, University of Limerick, Limerick, Ireland b Department of Computer Science and Software Engineering, University of Newcastle, Callaghan, NSW 2308, Australia c Stiftung caesar, Bonn, Germany |
| Abstract: | We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations. |
| Keywords: | Author Keywords: Level graphs Minimal non-planarity Maximum level planar subgraph |
| 本文献已被 ScienceDirect 等数据库收录！ | |