Stronger ILPs for the Graph Genus Problem.

DOI10.4230/LIPICS.ESA.2019.30MaRDI QIDQ5075767zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Tilo Wiedera

Publication date 11 May 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11151/pdf/LIPIcs-ESA-2019-30.pdf/

zbMATH Keywords

algorithm engineeringgenusinteger linear programming

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• A practical algorithm for the computation of the genus
• New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
• Local extrema in genus-stratified graphs
• scientific article; zbMATH DE number 5584120
• A note on approximating graph genus

Cites work

• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A Linear-Time Algorithm for Isomorphism of Graphs of Bounded Average Genus
• A pseudo-approximation for the genus of Hamiltonian graphs
• A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs
• An experimental comparison of four graph drawing algorithms.
• Approximation algorithms for Euler genus and related problems
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• Cycles to the rescue! Novel constraints to compute maximum planar subgraphs fast
• Das Geschlecht des vollständigen dreifärbbaren Graphen
• Das Geschlecht des vollständigen paaren Graphen
• Embeddings of graphs with no short noncontractible cycles
• Errors in graph embedding algorithms
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• Genus characterizes the complexity of certain graph problems: Some tight results
• Genus of the Cartesian product of triangles
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Network sparsification for Steiner problems on planar and bounded-genus graphs
• On embeddings of circulant graphs
• On the genus of \({\mathbb{Z}}_ 3\times {\mathbb{Z}}_ 3\times {\mathbb{Z}}_ 3\)
• On the genus of star graphs
• On the genus of the complete tripartite graph \(K_{n, n, 1}\)
• On the genus of the graph \(K_n\times K_2\) or the n-prism
• On the genus of the semidirect product of ℤ9 by ℤ3
• On the orientable genus of the Cartesian product of a complete regular tripartite graph with an even cycle.
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• The Bidimensional Theory of Bounded-Genus Graphs
• The Cartesian product of three triangles can be embedded into a subspace of genus 7
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• The genus of the n‐octahedron: Regular cases
• The genus of the complete tripartite graph Kmn,n,n
• The genus of the Gray graph is 7
• The graph genus problem is NP-complete

Cited in

(2)

• A practical algorithm for the computation of the genus
• An efficient genus algorithm based on graph rotations

Describes a project that uses

Uses Software

• SCIP
• OGDF

This page was built for publication: Stronger ILPs for the Graph Genus Problem.

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