Planar median graphs and cubesquare-graphs
Copyright policy )Planar median graphs and cubesquare-graphs
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 $\mathcal{O}(n\log n)$-time recognition algorithm to compute a decomposition of a planar median graph with $n$ vertices into cubes and square-graphs.
- Stockholm University Sweden
- Max Planck Institute for Mathematics in the Sciences Germany
- National University of Colombia Colombia
- Santa Fe Institute United States
- University of East Anglia United Kingdom
FOS: Computer and information sciences, Artificial intelligence, Discrete Mathematics (cs.DM), 101004 Biomathematics, Graph, Planar graphs; geometric and topological aspects of graph theory, 101004 Biomathematik, Clique-sum, Graph algorithms (graph-theoretic aspects), characterization, Connectivity, Planar median graph, Mesh Generation Algorithms, 102004 Bioinformatik, Indifference graph, Discrete mathematics, QS-graph, Computer Graphics and Computer-Aided Design, 004, recognition algorithm, Computational Theory and Mathematics, Pancyclic graph, planar median graph, Physical Sciences, Combinatorics (math.CO), 1-planar graph, Graph Theory and Algorithms, Embedding, Planar Graph Embedding, Computer Networks and Communications, Characterization, Cograph, Pathwidth, Metric dimension, hybercube, Planar graph, Chordal graph, Polyhedral graph, FOS: Mathematics, Hybercube, Mathematics - Combinatorics, 102004 Bioinformatics, Distance in graphs, Square-graph, Line graph, Computer science, Book embedding, square-graph, Networks on Chip in System-on-Chip Design, Recognition algorithm, Combinatorics, Outerplanar graph, Computer Science, Paths and cycles, Mathematics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Artificial intelligence, Discrete Mathematics (cs.DM), 101004 Biomathematics, Graph, Planar graphs; geometric and topological aspects of graph theory, 101004 Biomathematik, Clique-sum, Graph algorithms (graph-theoretic aspects), characterization, Connectivity, Planar median graph, Mesh Generation Algorithms, 102004 Bioinformatik, Indifference graph, Discrete mathematics, QS-graph, Computer Graphics and Computer-Aided Design, 004, recognition algorithm, Computational Theory and Mathematics, Pancyclic graph, planar median graph, Physical Sciences, Combinatorics (math.CO), 1-planar graph, Graph Theory and Algorithms, Embedding, Planar Graph Embedding, Computer Networks and Communications, Characterization, Cograph, Pathwidth, Metric dimension, hybercube, Planar graph, Chordal graph, Polyhedral graph, FOS: Mathematics, Hybercube, Mathematics - Combinatorics, 102004 Bioinformatics, Distance in graphs, Square-graph, Line graph, Computer science, Book embedding, square-graph, Networks on Chip in System-on-Chip Design, Recognition algorithm, Combinatorics, Outerplanar graph, Computer Science, Paths and cycles, Mathematics, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!