Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal B0-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of B0-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for B0-VPG graphs in the class of block graphs. © 2017, Springer Japan.

Registro:

Documento: Artículo
Título:Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs
Autor:Alcón, L.; Bonomo, F.; Mazzoleni, M.P.
Filiación:Departamento de Matemática, FCE-UNLP, La Plata, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Instituto de Investigación en Ciencias de la Computación (ICC), CONICET-Universidad de Buenos Aires, Buenos Aires, Argentina
CONICET and Departamento de Matemática, FCE-UNLP, La Plata, Argentina
Palabras clave:Block graphs; Forbidden induced subgraphs; Paths on a grid; Vertex intersection graphs
Año:2017
Volumen:33
Número:4
Página de inicio:653
Página de fin:664
DOI: http://dx.doi.org/10.1007/s00373-017-1791-6
Título revista:Graphs and Combinatorics
Título revista abreviado:Graphs Comb.
ISSN:09110119
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v33_n4_p653_Alcon

Referencias:

  • Asinowski, A., Cohen, E., Golumbic, M.C., Limouzy, V., Lipshteyn, M., Stern, M., Vertex intersection graphs of paths on a grid (2012) J. Graph Algorithms Appl, 16 (2), pp. 129-150
  • Bondy, J.A., Murty, U.S.R., (2007) Graph Theory, , Springer, New York
  • Brady, M.L., Sarrafzadeh, M., Stretching a knock-knee layout of multilayer wiring (1990) IEEE Trans. Comput, 39, pp. 148-151
  • Chaplick, S., Cohen, E., Stacho, J., Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid (2011) Lect. Notes Comput. Sci, 6986, pp. 319-330
  • Golumbic, M.C., Ries, B., On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs (2013) Graphs Comb, 29, pp. 499-517
  • Harary, F., Prins, G., The block-cutpoint-tree of a graph (1966) Publ. Math. Debr, 13, pp. 103-107
  • Kratochvíl, J., Matoušek, J., Intersection graphs of segments (1994) J. Comb. Theory Ser. B, 62, pp. 289-315
  • Molitor, P., A survey on wiring (1991) EIK J. Inf. Process. Cybern, 27, pp. 3-19
  • Sinden, F.W., Topology of thin film RC circuits (1966) Bell Syst. Tech. J, 45, pp. 1639-1662

Citas:

---------- APA ----------
Alcón, L., Bonomo, F. & Mazzoleni, M.P. (2017) . Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs. Graphs and Combinatorics, 33(4), 653-664.
http://dx.doi.org/10.1007/s00373-017-1791-6
---------- CHICAGO ----------
Alcón, L., Bonomo, F., Mazzoleni, M.P. "Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs" . Graphs and Combinatorics 33, no. 4 (2017) : 653-664.
http://dx.doi.org/10.1007/s00373-017-1791-6
---------- MLA ----------
Alcón, L., Bonomo, F., Mazzoleni, M.P. "Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs" . Graphs and Combinatorics, vol. 33, no. 4, 2017, pp. 653-664.
http://dx.doi.org/10.1007/s00373-017-1791-6
---------- VANCOUVER ----------
Alcón, L., Bonomo, F., Mazzoleni, M.P. Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs. Graphs Comb. 2017;33(4):653-664.
http://dx.doi.org/10.1007/s00373-017-1791-6