On some special classes of contact $B_0$-VPG graphs
On some special classes of contact $B_0$-VPG graphs
A graph G is a B0-VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B0-VPG graph if it is a B0-VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B0-VPG graphs within four special graph classes: chordal graphs, tree-cographs, P4-tidy graphs and P5-free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B0-VPG graphs.
Fil: Rean, Mariano Leonardo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
Fil: Mazzoleni, María Pía. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina
Fil: Ries, Bernard. Universite de Fribourg (unifr);
- National University of La Plata Argentina
- National Scientific and Technical Research Council Argentina
- University of Fribourg Switzerland
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, P4-tidy graph, \( P_5\)-free graph, chordal graph, TREE-COGRAPH, Graph algorithms (graph-theoretic aspects), P5-free graph, FOS: Mathematics, https://purl.org/becyt/ford/1.1, Mathematics - Combinatorics, https://purl.org/becyt/ford/1, Ciencias Exactas, P4-TIDY GRAPH, Matemática, contact \(B_0\)-VPG graph, CONTACT B0-VPG GRAPH, P5-FREE GRAPH, \( P_4\)-tidy graph, Graph theory (including graph drawing) in computer science, tree-cograph, CHORDAL GRAPH, Structural characterization of families of graphs, Combinatorics (math.CO), contact B 0-VPG graph, 05C99, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, P4-tidy graph, \( P_5\)-free graph, chordal graph, TREE-COGRAPH, Graph algorithms (graph-theoretic aspects), P5-free graph, FOS: Mathematics, https://purl.org/becyt/ford/1.1, Mathematics - Combinatorics, https://purl.org/becyt/ford/1, Ciencias Exactas, P4-TIDY GRAPH, Matemática, contact \(B_0\)-VPG graph, CONTACT B0-VPG GRAPH, P5-FREE GRAPH, \( P_4\)-tidy graph, Graph theory (including graph drawing) in computer science, tree-cograph, CHORDAL GRAPH, Structural characterization of families of graphs, Combinatorics (math.CO), contact B 0-VPG graph, 05C99, 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).0 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!