- 2-subcoloring is NP-complete for planar comparability graphs
2017/08/31 by Pascal Ochem · 1 citation
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Clique-sum #Cograph #Combinatorics #Comparability #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Indifference graph #Line graph #Mathematics #Maximal independent set #Outerplanar graph #Partition (number theory) #Pathwidth #Planar graph #Vertex (graph theory) #graph theory and CDMA systems
- Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
2014/02/28 by Daniel J. Harvey, David R. Wood · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Combinatorics #Treewidth #Mathematics #Discrete mathematics #Disjoint sets #Graph minor #Graph #Vertex (graph theory) #Cubic graph #Outerplanar graph #Partial k-tree #Graph power #1-planar graph #Line graph #Pathwidth #Voltage graph
- Two-Page Book Embeddings of 4-Planar Graphs
2014/01/01 by Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Cellular Automata and Applications #Book embedding #Planar graph #Planar #Outerplanar graph #Planar straight-line graph #1-planar graph #Embedding #Combinatorics #Hamiltonian path #Pathwidth #Class (philosophy) #Chordal graph #Quadratic equation #Mathematics #Computer science #Discrete mathematics #Indifference graph #Graph #Artificial intelligence #Line graph #Geometry #Computer graphics (images)
- On the Complexity of Metric Dimension
2012/01/01 by Josep Dı́az, Josep Díaz, Olli Pottonen +3 · 9 citations
Computer Science · Mathematics · #1-planar graph #Bounded function #Chordal graph #Combinatorics #Dimension (graph theory) #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Metric (unit) #Metric dimension #Outerplanar graph #Pathwidth #Planar graph #Time complexity
- Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
2011/12/09 by Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Biconnected graph #Book embedding #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Embedding #Graph #Graph power #Intersection (aeronautics) #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph #Planar straight-line graph #Time complexity #Vertex (graph theory)
- The LBFS Structure and Recognition of Interval Graphs
2009/12/11 by Derek G. Corneil, Stephan Olariu, Lorna Stewart · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Constraint Satisfaction and Optimization #Interval graph #Chordal graph #Combinatorics #Indifference graph #Pathwidth #Mathematics #Split graph #Intersection graph #Discrete mathematics #Block graph #Lexicographical order #Intersection (aeronautics) #Outerplanar graph #Trapezoid graph #Graph #Interval (graph theory) #Line graph #1-planar graph
- Graphs whose flow polynomials have only integral roots
2009/08/03 by Joseph P. S. Kung, Kung, Joseph P. S., Gordon F. Royle +2 · 1 citation
Computer Science · Mathematics · #05B35 #1-planar graph #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Chordal graph #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #Graph #Graph theory and applications #Graphic matroid #Indifference graph #Line graph #Mathematics #Matroid #Outerplanar graph #Pathwidth #Planar graph #Treewidth #math.CO #msc:05B35
- On the Path-Width of Planar Graphs
2009/01/01 by Omid Amini, Florian Huc, Stéphane Pérennès · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory #Pathwidth #Combinatorics #Mathematics #Planar graph #Outerplanar graph #Discrete mathematics #1-planar graph #Graph #Chordal graph #Line graph
- The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
2009/01/01 by David Eppstein · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Bipartite graph #Book embedding #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Digital Image Processing Techniques #Discrete mathematics #Embedding #Graph #Graph embedding #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph #Topology (electrical circuits) #Vertex (graph theory)
- Linearity of grid minors in treewidth with applications through bidimensionality
2008/01/01 by Erik D. Demaine, MohammadTaghi Hajiaghayi, Mohammadtaghi Hajiaghayi · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph minor #Limits and Structures in Graph Theory #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph
- The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing
2007/09/30 by David Eppstein · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Book embedding #Computational Geometry and Mesh Generation #Embedding #Graph #Graph embedding #Line graph #Outerplanar graph #Planar graph #Topological and Geometric Data Analysis #Topological graph theory #cs.CG #math.CO
- On self duality of pathwidth in polyhedral graph embeddings
2007/01/30 by Fedor V. Fomin, Dimitrios M. Thilikos · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Graph Labeling and Dimension Problems #Pathwidth #Mathematics #Combinatorics #Outerplanar graph #Planar graph #Discrete mathematics #Bounded function #Graph #Dual graph #Line graph
- Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
2007/01/01 by Anne Berry, Martin Charles Golumbic, Marina Lipshteyn · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #Complexity and Algorithms in Graphs #Chordal graph #Combinatorics #Split graph #Mathematics #Interval graph #Indifference graph #Pathwidth #Partition (number theory) #Discrete mathematics #Treewidth #Outerplanar graph #Graph #1-planar graph #Line graph
- Pathwidth of outerplanar graphs
2006/12/22 by David Coudert, Florian Huc, Jean‐Sébastien Sereni · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Graph Labeling and Dimension Problems #Pathwidth #Mathematics #Combinatorics #Outerplanar graph #Discrete mathematics #Graph #Line graph
- On simultaneous planar graph embeddings
2006/07/04 by Peter Braß, Peter Brass, Eowyn Čenek +11 · 3 citations
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Book embedding #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Embedding #Geometry #Graph #Grid #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar #Planar graph #Planar straight-line graph #Structural Analysis and Optimization
- Graph minor theory
2005/10/24 by László Lovász · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Robertson–Seymour theorem #Planar graph #Discrete mathematics #Outerplanar graph #Pathwidth #1-planar graph #Chordal graph #Minor (academic) #Conjecture #Indifference graph #Graph minor #Graph #Line graph #Voltage graph
- Embedding Planar Graphs In Seven Pages
2005/08/25 by Lenwood S. Heath · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Book embedding #Planar graph #Embedding #Planar straight-line graph #Planar #Outerplanar graph #Polyhedral graph #Conjecture #Computer science #Graph #Combinatorics #Graph embedding #Discrete mathematics #Mathematics #1-planar graph #Pathwidth #Theoretical computer science #Chordal graph #Line graph #Artificial intelligence #Computer graphics (images)
- On chordal graphs and their chromatic polynomials
2003/12/01 by Geir Agnarsson · 1 citation
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Chordal graph #Mathematics #Corollary #Chromatic polynomial #Combinatorics #Chromatic scale #Interval graph #Discrete mathematics #Graph #Outerplanar graph #Pathwidth #1-planar graph #Line graph
- Graph Minors. XVI. Excluding a non-planar graph
2003/04/30 by Neil Robertson, Paul Seymour, P.D Seymour · 8 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph minor #Humanities #Line graph #Mathematics #Minor (academic) #Outerplanar graph #Pathwidth #Philosophy #Planar graph #Robertson–Seymour theorem #Voltage graph
- Pathwidth of Planar and Line Graphs
2003/03/01 by Fedor V. Fomin · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph
- Approximation of pathwidth of outerplanar graphs
2002/05/01 by Hans L. Bodlaender, Fedor V. Fomin · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chordal graph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Treewidth
- Triangle-Free Planar Graphs and Segment Intersection Graphs
2002/01/01 by Natalia de Castro, Francisco Javier Molina Cobos, Juan Carlos Dana +2 · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Optimization and Packing Problems #Chordal graph #Intersection (aeronautics) #Combinatorics #Planar graph #Planar #Outerplanar graph #Computer science #1-planar graph #Mathematics #Pathwidth #Graph #Geography #Line graph #Computer graphics (images) #Cartography
- Drawing Graphs
2001/01/01 by Michael Kaufmann, Dorothea Wagner · 7 citations
Computer Science · Engineering · #Architecture and Computational Design #Book embedding #Computer science #Data Visualization and Analytics #Graph #Graph drawing #Line graph #Outerplanar graph #Pathwidth #Planar graph #Theoretical computer science
- Diameter and Treewidth in Minor-Closed Graph Families
1999/07/20 by David Eppstein · 11 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph minor #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph #math.CO #msc:05C75
- A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments
1998/05/01 by Jurek Czyzowicz, Evangelos Kranakis, Jorge Urrutia · 1 citation
Computer Science · Environmental Science · Mathematics · #1-planar graph #Bipartite graph #Book embedding #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Digital Image Processing Techniques #Discrete mathematics #Geometry #Graph #Graph drawing #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar #Planar graph #Planar straight-line graph #Plane (geometry) #Remote Sensing and LiDAR Applications
- The Colin de Verdi�re number and sphere representations of a graph
1997/12/01 by Andrew Kotlov, L�szl� Lov�sz, Santosh Vempala · 1 citation
Mathematics · #Advanced Differential Equations and Dynamical Systems #Advanced Topics in Algebra #Characterization (materials science) #Combinatorics #Complement (music) #Computer science #Discrete mathematics #Graph #Invariant (physics) #Line graph #Mathematics #Mathematics and Applications #Outerplanar graph #Pathwidth #Planar #Planar graph
- Characterizations and algorithmic applications of chordal graph embeddings
1997/11/01 by Andreas Parra, Petra Scheffler · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chordal graph #Cograph #Combinatorics #Comparability graph #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Indifference graph #Interval graph #Line graph #Mathematics #Outerplanar graph #Pathwidth #Split graph #Treewidth
- TREEWIDTH OF CIRCLE GRAPHS
1996/06/01 by Ton Kloks · 2 citations
Computer Science · Mathematics · #Interconnection Networks and Systems #Advanced Graph Theory Research #Graph Theory and Algorithms #Treewidth #Combinatorics #Partial k-tree #Circle graph #Mathematics #Block graph #Chordal graph #Outerplanar graph #Discrete mathematics #Tree-depth #Split graph #Pathwidth #Clique-sum #1-planar graph #Line graph #Graph
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
1995/09/01 by Yaw-Ling Lin, Steven Skiena · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Robotic Path Planning Algorithms #Visibility graph #Combinatorics #Visibility polygon #Visibility #Mathematics #Pathwidth #Vertex (graph theory) #Discrete mathematics #Polygon (computer graphics) #Indifference graph #Maximal independent set #Planar graph #Outerplanar graph #Vertex cover #1-planar graph #Time complexity #Graph #Chordal graph #Simple polygon #Computer science #Line graph #Regular polygon #Geometry #Optics
- Quickly Excluding a Planar Graph
1994/11/01 by Neil Robertson, N. Robertson, Paul Seymour +3 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Bounded function #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Graph #Graph minor #Graph power #Line graph #Mathematics #Minor (academic) #Outerplanar graph #Pathwidth #Planar #Planar graph #Upper and lower bounds
more