- 3-Colouring Planar Graphs
2025/07/03 by Vida Dujmović, Dujmović, Vida, Pat Morin +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Graph #Graph Labeling and Dimension Problems #Monochromatic color #Planar #Planar graph #Upper and lower bounds
- Negative-Weight Single-Source Shortest Paths in Near-linear Time
2022/03/07 by Aaron Bernstein, Danupon Nanongkai, Bernstein, Aaron +4 · 2 voices · 20 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Binary logarithm #Combinatorial algorithms #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Mathematics #Planar graph #Randomized algorithm #Running time #Simple (philosophy) #Tilde #Time complexity
- Planar Graphs Have Bounded Queue-Number
2019/04/30 by Vida Dujmović, Gwenaël Joret, Piotr Micek +3 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Bounded function #Clique-sum #Computational Geometry and Mesh Generation #Graph product #Indifference graph #Limits and Structures in Graph Theory #Pathwidth #Planar graph #Tree-depth #Treewidth
- Excluded minors in cubic graphs
2019/02/19 by Neil Robertson, Paul Seymour, Robin Thomas · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics #Computer science #Cubic graph #Discrete mathematics #Embedding #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Partition (number theory) #Petersen graph #Planar graph #Polyhedral graph #Vertex (graph theory) #Voltage graph
- Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large\n Angles
2018/08/25 by Philipp Kindermann, Fabrizio Montecchiani, Kindermann, Philipp +5 · 1 citation
Computer Science · Mathematics · #1-planar graph #Book embedding #Chordal graph #Combinatorics #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer science #Crossing number (knot theory) #Embedding #Enhanced Data Rates for GSM Evolution #FOS: Computer and information sciences #Geometry #Graph #Mathematical analysis #Mathematics #Planar #Planar graph #Resolution (logic) #Upper and lower bounds #Vertex (graph theory)
- A Large Set of Torus Obstructions and How They Were Discovered
2018/01/25 by Wendy Myrvold, Jennifer Woodcock · 2 citations
Computer Science · Engineering · Mathematics · #Digital and Cyber Forensics #Integrated Circuits and Semiconductor Failure Analysis #Mechanical stress and fatigue analysis #Torus #Embedding #Mathematics #Set (abstract data type) #Planar graph #Graph #Book embedding #Quadratic equation #Graph embedding #Combinatorics #Discrete mathematics #Algorithm #Theoretical computer science #1-planar graph #Computer science #Chordal graph #Artificial intelligence #Geometry
- 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
- Visibility graphs, dismantlability, and the cops and robbers game
2017/07/05 by Anna Lubiw, Jack Snoeyink, Hamideh Vosoughpour · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Euclidean geometry #Geography #Geometry #Graph #Guidance and Control Systems #Mathematics #Planar graph #Polygon (computer graphics) #Regular polygon #Robotic Path Planning Algorithms #Telecommunications #Visibility #Visibility graph
- Polynomial Bounds for the Grid-Minor Theorem
2016/12/17 by Chandra Chekuri, Julia Chuzhoy · 7 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph minor #Interconnection Networks and Systems #Line graph #Mathematics #Minor (academic) #Partial k-tree #Pathwidth #Planar graph #Polynomial #Robertson–Seymour theorem #Tree decomposition #Tree-depth #Treewidth #Upper and lower bounds #Voltage graph
- Algorithmic Aspects of Regular Graph Covers
2016/09/10 by Jiří Fiala, Jiřı́ Fiala, Pavel Klavík +7 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Bijection #Combinatorics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph homomorphism #Graph isomorphism #Graph power #Group Theory (math.GR) #Homomorphism #Isomorphism (crystallography) #Limits and Structures in Graph Theory #Line graph #Mathematics #Planar graph #Time complexity #Ubiquitin and proteasome pathways #cs.DM #math.CO #math.GR
- The Locality of Distributed Symmetry Breaking
2016/06/28 by Leonid Barenboim, Michael Elkin, Seth Pettie +1 · 23 citations
Computer Science · Mathematics · #Algorithm #Arboricity #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Cryptography and Data Security #Degeneracy (biology) #Discrete mathematics #Graph #Log-log plot #Matching (statistics) #Mathematics #Optimization and Search Problems #Planar graph #Running time #Time complexity #Upper and lower bounds #Vertex (graph theory)
- Three-edge-colouring doublecross cubic graphs
2016/01/05 by Katherine Edwards, Daniel P. Sanders, Paul Seymour +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Materials and Mechanics #Combinatorics #Cubic graph #Discrete mathematics #Graph #Graph minor #Line graph #Mathematics #Petersen graph #Planar graph #Vertex (graph theory) #Voltage graph #graph theory and CDMA systems
- Edge-colouring eight-regular planar graphs
2015/05/18 by Maria Chudnovsky, Katherine Edwards, Paul Seymour · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complement (music) #Computer science #Conjecture #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Graph #Mathematics #Planar graph #graph theory and CDMA systems
- 1-Planar Graphs have Constant Book Thickness
2015/01/01 by Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Book embedding #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Discrete mathematics #Embedding #Graph #Graph power #Line graph #Mathematical analysis #Mathematics #Optimization and Search Problems #Path graph #Planar graph #Planar straight-line graph #Upper and lower bounds
- 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)
- Polynomial algorithms for open plane graph and subgraph isomorphisms
2013/05/27 by Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel +2 · 1 citation
Computer Science · Mathematics · #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete mathematics #Geometry #Graph #Graph Theory and Algorithms #Indifference graph #Line graph #Mathematics #Pathwidth #Planar graph #Plane (geometry) #Time complexity
- 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
- Selected Slither Link Variants are NP-complete
2012/01/01 by Jonas K ouml lker · 1 citation
Computer Science · Social Sciences · Psychology · Mathematics · #Artificial Intelligence in Games #Digital Games and Media #Educational Games and Gamification #Computer science #Link (geometry) #Graph #Set (abstract data type) #Planar graph #NP-complete #Combinatorics #Theoretical computer science #Algorithm #Time complexity #Mathematics #Computer network #Programming language
- 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)
- Deterministic Distributed Vertex Coloring in Polylogarithmic Time
2011/10/01 by Leonid Barenboim, Michael Elkin · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Arboricity #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Deterministic algorithm #Discrete mathematics #Graph #Mathematics #Planar graph #Randomized algorithm #Running time #Vertex (graph theory)
- Fast Minor Testing in Planar Graphs
2011/09/07 by Isolde Adler, Frederic Dorn, Fedor V. Fomin +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Mathematics #Minor (academic) #Optimization and Search Problems #Planar graph #Subroutine #Vertex (graph theory)
- Linkless and flat embeddings in 3-space and the unknot problem
2010/06/13 by Ken‐ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Geometric and Algebraic Topology #Computational Geometry and Mesh Generation #Unknot #Combinatorics #Embedding #Mathematics #Converse #Book embedding #Disjoint sets #Discrete mathematics #Planar graph #Knot (papermaking) #Graph #Series (stratigraphy) #Chordal graph #1-planar graph #Computer science #Geometry
- On well-covered triangulations: Part III
2010/03/03 by Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Degree (music) #Discrete mathematics #Geometry #Graph #Graph Labeling and Dimension Problems #Mathematics #Planar graph #Triangulation #graph theory and CDMA systems
- On Barnette’s conjecture
2010/03/03 by Jan Florek · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Conjecture #Discrete mathematics #Face (sociological concept) #Graph #Hamiltonian (control theory) #Hamiltonian path #Limits and Structures in Graph Theory #Mathematics #Planar graph #graph theory and CDMA systems
- Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances
2009/09/05 by Paul Bonsma, Luis Cereceda · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bipartite graph #Combinatorics #Computational complexity theory #Discrete mathematics #Graph #Limits and Structures in Graph Theory #Mathematics #Optimization and Search Problems #PSPACE #Planar graph #Vertex (graph theory)
- Graphs whose flow polynomials have only integral roots
2009/08/03 by Joseph P. S. Kung, Gordon Royle, Kung, Joseph P. S. +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
- Planar Graph Isomorphism is in Log-Space
2009/07/01 by Samir Datta, Nutan Limaye, Prajakta Nimbhorkar +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Theory and Algorithms #Complexity and Algorithms in Graphs #Combinatorics #Mathematics #Planar graph #Upper and lower bounds #Discrete mathematics #Graph
- 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)
- On star and caterpillar arboricity
2008/03/12 by Daniel Gonçalves, Pascal Ochem · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Arboricity #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Dense graph #Discrete mathematics #Girth (graph theory) #Graph #Interconnection Networks and Systems #Mathematical analysis #Mathematics #Planar #Planar graph #Star (game theory)
more