Face covers and the genus problem for apex graphs
From MaRDI portal
Publication:1850536
DOI10.1006/jctb.2000.2026zbMath1025.05019OpenAlexW1974224894MaRDI QIDQ1850536
Publication date: 10 December 2002
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.2000.2026
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
CPG graphs: some structural and hardness results ⋮ On graphs whose eternal vertex cover number and vertex cover number coincide ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ 1-extendability of independent sets ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Splitting plane graphs to outerplanarity ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Combinatorial conjectures that imply local log-concavity of graph genus polynomials ⋮ Roman domination and independent Roman domination on graphs with maximum degree three ⋮ Computing maximum matchings in temporal graphs ⋮ On 3-degree 4-chordal graphs ⋮ Grid induced minor theorem for graphs of small degree ⋮ Fractals for Kernelization Lower Bounds ⋮ \(\mathcal{P}\)-apex graphs ⋮ The complexity of the Clar number problem and an exact algorithm ⋮ Unnamed Item ⋮ Optimizing phylogenetic diversity with ecological constraints ⋮ On directed covering and domination problems ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ 1-extendability of independent sets ⋮ Secure total domination in graphs: bounds and complexity ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ A Characterization of $K_{2,4}$-Minor-Free Graphs ⋮ On the complexity of anchored rectangle packing ⋮ Some vertex/edge-degree-based topological indices of \(r\)-apex trees ⋮ Local search for the minimum label spanning tree problem with bounded color classes. ⋮ Labeled \(K_{2,t}\) minors in plane graphs ⋮ On maximum independent set of categorical product and ultimate categorical ratios of graphs ⋮ On reconfigurability of target sets ⋮ Embeddings of planar graphs that minimize the number of long-face cycles ⋮ On the complexity of the vector connectivity problem ⋮ Regular independent sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On obstructions to small face covers in planar graphs
- Some simplified NP-complete graph problems
- Triangulating a surface with a prescribed graph
- A special planar satisfiability problem and a consequence of its NP- completeness
- Uniqueness and minimality of large face-width embeddings of graphs
- The graph genus problem is NP-complete
- On the Complexity of Covering Vertices by Faces in a Planar Graph
- The Planar Hamiltonian Circuit Problem is NP-Complete
