Tree-Layout Based Graph Classes: Proper Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2024

Tree-Layout Based Graph Classes: Proper Chordal Graphs

Résumé

Many important graph classes are characterized by means of layouts (a vertex ordering) excluding some patterns. For example, a graph G = (V, E) is a proper interval graph if and only if G has a layoutLsuchthatforeverytripleofverticessuchthatx≺L y≺L z,ifxz∈E,thenxy∈Eand yz ∈ E. Such a triple x, y, z is called an indifference triple. In this paper, we investigate the concept of excluding a set of patterns in tree-layouts rather than layouts. A tree-layout TG = (T,r,ρG) of a graph G = (V,E) is a tree T rooted at some node r and equipped with a one-to-one mapping ρG between V and the nodes of T such that for every edge xy ∈ E, either x is an ancestor of y, denoted x ≺TG y, or y is an ancestor of x. Excluding patterns in a tree-layout is now defined using the ancestor relation. This leads to an unexplored territory of graph classes. In this paper, we initiate the study of such graph classes with the class of proper chordal graphs defined by excluding indifference triples in tree-layouts. Our results combine characterization, compact and canonical representation as well as polynomial time algorithms for the recognition and the graph isomorphism of proper chordal graphs. For this, one of the key ingredients is the introduction of the concept of FPQ-hierarchy generalizing the celebrated PQ-tree data-structure.
Fichier principal
Vignette du fichier
proper_chordal_SIDMA.pdf (550.62 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-04720130 , version 1 (03-10-2024)

Identifiants

Citer

Christophe Paul, Evangelos Protopapas. Tree-Layout Based Graph Classes: Proper Chordal Graphs. STACS 2024 - 41st International Symposium on Theoretical Aspects of Computer Science, Mar 2024, Clermont-Ferrand, France. pp.55:1--55:18, ⟨10.4230/LIPICS.STACS.2024.55⟩. ⟨lirmm-04720130⟩
11 Consultations
3 Téléchargements

Altmetric

Partager

More