All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Graph Product Structure for h-Framed Graphs

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00129307" target="_blank" >RIV/00216224:14330/22:00129307 - isvavai.cz</a>

  • Result on the web

    <a href="https://doi.org/10.4230/LIPIcs.ISAAC.2022.23" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2022.23</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2022.23" target="_blank" >10.4230/LIPIcs.ISAAC.2022.23</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Graph Product Structure for h-Framed Graphs

  • Original language description

    Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊ h/2 ⌋+⌊ h/3 ⌋-1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊ 33/2(k+3 ⌊ k/2⌋ -3)⌋ to ⌊ 33/2 (3⌊ k/2 ⌋+⌊ k/3 ⌋-1) ⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

    <a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2022

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    33rd International Symposium on Algorithms and Computation (ISAAC 2022)

  • ISBN

    9783959772587

  • ISSN

    1868-8969

  • e-ISSN

  • Number of pages

    15

  • Pages from-to

    „23:1“-„23:15“

  • Publisher name

    Schloss Dagstuhl

  • Place of publication

    Dagstuhl, Germany

  • Event location

    Seoul, Korea

  • Event date

    Dec 19, 2022

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article