Tools
Tools
Seemann, Carsten R., Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435, Stadler, Peter F. and Hellmuth, Marc
(2023)
Planar median graphs and cubesquare-graphs.
Discrete Applied Mathematics, 331.
pp. 38-58.
ISSN 0166-218X
Preview |
PDF (1-s2.0-S0166218X23000203-main)
- Published Version
Available under License Creative Commons Attribution. Download (618kB) | Preview |
Abstract
Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several novel characterizations of planar median graphs. More specifically, we characterize when a planar graph G is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in G, and also in terms of subgraphs of G that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of G. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square-graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square-graphs by a sequence of “square-boundary” amalgamations. These considerations also lead to an O(n log n)-time recognition algorithm to compute a decomposition of a planar median graph with n vertices into cubes and square-graphs.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | characterization,hybercube,planar median graph,qs-graph,recognition algorithm,square-graph,discrete mathematics and combinatorics,applied mathematics ,/dk/atira/pure/subjectarea/asjc/2600/2607 |
| Faculty \ School: | Faculty of Science > School of Computing Sciences |
| UEA Research Groups: | Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Groups > Computational Biology |
| Related URLs: | |
| Depositing User: | LivePure Connector |
| Date Deposited: | 27 Jan 2023 10:31 |
| Last Modified: | 08 Jun 2023 16:30 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/90835 |
| DOI: | 10.1016/j.dam.2023.01.022 |
Downloads
Downloads per month over past year
Actions (login required)
 |
View Item |