Thickness and colorability of geometric graphs (Q679741): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
Normalize DOI.
 
(2 intermediate revisions by 2 users not shown)
Property / DOI
 
Property / DOI: 10.1016/j.comgeo.2016.03.003 / rank
Normal rank
 
Property / cites work
 
Property / cites work: Thickness and Colorability of Geometric Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5735733 / rank
 
Normal rank
Property / cites work
 
Property / cites work: THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5732335 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric Thickness of Complete Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Determining the thickness of graphs is NP-hard / rank
 
Normal rank
Property / cites work
 
Property / cites work: The thickness of graphs: A survey / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4657580 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On representations of some thickness-two graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounded-degree graphs have arbitrarily large geometric thickness / rank
 
Normal rank
Property / cites work
 
Property / cites work: The geometric thickness of low degree graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph treewidth and geometric thickness parameters / rank
 
Normal rank
Property / cites work
 
Property / cites work: On graph thickness, geometric thickness, and separator theorems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Thickness and coarseness of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph Drawing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Every planar map is four colorable. I: Discharging / rank
 
Normal rank
Property / cites work
 
Property / cites work: 25 pretty graph colouring problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of the empire colouring problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Enumerating order types for small point sets with applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simultaneous Embedding of Planar Graphs with Few Bends / rank
 
Normal rank
Property / cites work
 
Property / cites work: SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximizing the Degree of (Geometric) Thickness-t Regular Graphs / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1016/J.COMGEO.2016.03.003 / rank
 
Normal rank

Latest revision as of 00:38, 10 December 2024

scientific article
Language Label Description Also known as
English
Thickness and colorability of geometric graphs
scientific article

    Statements

    Thickness and colorability of geometric graphs (English)
    0 references
    0 references
    0 references
    0 references
    19 January 2018
    0 references
    The authors consider the thickness and geometric thickness of graphs. They give an example of a graph with thickness equal to 2 and geometric thickness equal to 3. They prove that the problem of recognizing geometric thickness is NP-hard even for graphs with geometric thickness equal to 2. Moreover, they give the proof of NP-hardness of \((4t-1)\)-coloring graphs with geometric thickness \(t\). The paper improves known results in this topic.
    0 references
    complete graph
    0 references
    geometric thickness
    0 references
    coloring
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references