Characterising Chordal Contact-VPG Graphs
2018, International Symposium on Combinatorial Optimization, 89-100, 2018Citas: 2
Agregar PDF Importar citas SCRAPME Plots Conexiones
Autor(es)
Flavia Bonomo and Maria Pia Mazzoleni and Mariano Leonardo Rean and Bernard Ries
Abstract
A graph G is a -VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact -VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph characterisation of contact -VPG graphs within the class of chordal graphs and provide a polynomial-time algorithm for recognising these graphs.
Plot de citas
Citas
| # | Title | Year | Source | Authors | |
|---|---|---|---|---|---|
| 1 | Survey of intersection graphs, fuzzy graphs and neutrosophic graphs | 2024 | … and Uncertainization: Fuzzy, Neutrosophic, Soft, Rough … | T Fujita | |
| 2 | On some special classes of contact B0-VPG graphs | 2022 | Discrete Applied … | F Bonomo-Braberman, MP Mazzoleni, ML Rean | |
| 3 | Characterising circular-arc contact B0–VPG graphs | 2020 | Discrete Applied … | F Bonomo-Braberman, E Galby, CL Gonzalez |