- Coset Intersection Graphs for Groups
2013/04/22 by Jack Button, Maurice Chiodo, Mariano Zeron-Medina Laris · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Coset #Finite Group Theory Research #Group (periodic table) #Intersection (aeronautics) #Intersection graph #Intersection number #Limits and Structures in Graph Theory #math.GR #math.HO #msc:20E99
- Triangle-free intersection graphs of line segments with large chromatic number
2012/09/30 by Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Block graph #Bounded function #Chordal graph #Chromatic scale #Clique number #Computational Geometry and Mesh Generation #Conjecture #Graph #Intersection (aeronautics) #Intersection graph #cs.CG #cs.DM #math.CO #msc:05C15 #msc:05C62
- Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs
2011/07/26 by Emeric Gioan, Christophe Paul · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bijection #Block graph #Chordal graph #Cograph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Indifference graph #Intersection graph #Line graph #Mathematics #Modular decomposition #Pathwidth #Split graph
- 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
- Density theorems for bipartite graphs and related Ramsey-type results
2009/03/01 by Jacob Fox, Benny Sudakov · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Bipartite graph #Cograph #Combinatorics #Dense graph #Discrete mathematics #Extremal graph theory #Graph #Intersection graph #Limits and Structures in Graph Theory #Line graph #Mathematical proof #Mathematics #Pathwidth #Ramsey theory #Ramsey's theorem #Triangle-free graph #Voltage graph
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
2005/01/01 by Thomas Erlebach, Klaus Jansen, Eike Seidel · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Unit disk graph #Combinatorics #Intersection graph #Mathematics #Chordal graph #Indifference graph #Disjoint sets #Maximal independent set #Planar graph #Pathwidth #Time complexity #Independent set #Discrete mathematics #Approximation algorithm #1-planar graph #Graph #Computer science #Line graph
- Tolerance Graphs
2004/02/12 by Martin Charles Golumbic, Ann N. Trenk · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Mathematical proof #Computer science #Permutation graph #Graph theory #Indifference graph #Theoretical computer science #Chordal graph #Intersection graph #Combinatorics #Discrete mathematics #Graph #Mathematics #Line graph
- Testing bipartiteness of geometric intersection graphs
2003/07/31 by David Eppstein · 1 citation
Computer Science · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Data Management and Algorithms #Discrete mathematics #Euclidean geometry #Euclidean space #Geometry #Graph #Graph Theory and Algorithms #Intersection (aeronautics) #Intersection graph #Line graph #Line segment #Mathematics #Pathwidth #Planar graph #Plane (geometry) #Treewidth #cs.CG
- Unit disk graph recognition is NP-hard
1998/01/01 by Heinz Breu, David Kirkpatrick, David G. Kirkpatrick · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Conjecture #Discrete mathematics #Geometry #Graph #Intersection graph #Line graph #Mathematics #Planar graph #Sphericity #Unit disk graph
- On grid intersection graphs
1991/01/01 by I.Ben-Arroyo Hartman, Irith Ben‐Arroyo Hartman, Ilan Newman +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Geometry #Graph #Grid #Intersection (aeronautics) #Intersection graph #Line graph #Mathematics #Planar graph #Plane (geometry) #Square tiling #graph theory and CDMA systems
- Unit disk graphs
1990/12/01 by Brent N. Clark, Charles J. Colbourn, David Johnson +1 · 12 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Dominating set #Graph #Grid #Indifference graph #Intersection (aeronautics) #Intersection graph #Line graph #Mathematics #Maximal independent set #Mobile Ad Hoc Networks #Pathwidth #Split graph #Unit disk #Unit disk graph #Vertex (graph theory)
- Intersection graphs of curves in the plane
1976/08/01 by G. Ehrlich, G Ehrlich, Shimon Even +3 · 6 citations
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Geometry #Graph #Independent set #Intersection (aeronautics) #Intersection graph #Line graph #Mathematics #Maximal independent set #Optimization and Packing Problems #Plane (geometry) #Plane curve