PROPERTIES OF ARRANGEMENT GRAPHS

DOI10.1142/S0218195903001281MaRDI QIDQ4661879zbMATH OpenFDO

Authors Prosenjit Bose, Hazel Everett, S. Wismath

Publication date 30 March 2005

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218195903001281

zbMATH Keywords

Hamiltonian pathinducing pathinducing polygon

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• On Inducing Polygons and Related Problems
• scientific article; zbMATH DE number 1744069
• Every simple arrangement of n lines contains an inducing simple n-gon
• Hamiltonicity and colorings of arrangement graphs

Cites work

• A simple algorithm for determining the envelope of a set of lines
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• Multidimensional Sorting
• On Envelopes of Arrangements of Lines

Cited in

(10)

• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• Variants of the segment number of a graph
• INDUCING POLYGONS OF LINE ARRANGEMENTS
• On inducing polygons and related problems
• On Envelopes of Arrangements of Lines
• scientific article; zbMATH DE number 1445299 (Why is no real title available?)
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• On degree sequences and eccentricities in pseudoline arrangement graphs
• Hamiltonicity and colorings of arrangement graphs
• Graph properties of graph associahedra

This page was built for publication: PROPERTIES OF ARRANGEMENT GRAPHS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4661879)