Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Planar median graphs and cubesquare-graphs
Stockholms universitet, Naturvetenskapliga fakulteten, Matematiska institutionen.ORCID-id: 0000-0002-1620-5508
Antal upphovsmän: 42023 (Engelska)Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 331, s. 38-58Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

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-boundaryamalgamations. 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. 

Ort, förlag, år, upplaga, sidor
2023. Vol. 331, s. 38-58
Nyckelord [en]
Planar median graph, Hybercube, Square-graph, QS-graph, Characterization, Recognition algorithm
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:su:diva-217363DOI: 10.1016/j.dam.2023.01.022ISI: 000968643700001Scopus ID: 2-s2.0-85147019738OAI: oai:DiVA.org:su-217363DiVA, id: diva2:1759925
Tillgänglig från: 2023-05-29 Skapad: 2023-05-29 Senast uppdaterad: 2023-05-29Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Hellmuth, Marc

Sök vidare i DiVA

Av författaren/redaktören
Moulton, VincentStadler, Peter F.Hellmuth, Marc
Av organisationen
Matematiska institutionen
I samma tidskrift
Discrete Applied Mathematics
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 50 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf