Approximation Algorithms for Euler Genus and Related Problems (Q4581910): Difference between revisions

@@ Property / cites work @@
+A kuratowski theorem for the projective plane
@@ Property / cites work: A kuratowski theorem for the projective plane / rank @@
+Normal rank
@@ Property / cites work @@
+A framework for solving VLSI graph layout problems
+Normal rank
@@ Property / cites work @@
+Separating and nonseparating disjoint homotopic cycles in graph embeddings
+Normal rank
@@ Property / cites work @@
+Hardness of approximation for crossing number
@@ Property / cites work: Hardness of approximation for crossing number / rank @@
+Normal rank
@@ Property / cites work @@
+Finding shortest non-trivial cycles in directed graphs on surfaces
+Normal rank
@@ Property / cites work @@
+Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
+Normal rank
@@ Property / cites work @@
+Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
+Normal rank
@@ Property / cites work @@
+A Better Approximation Algorithm for Finding Planar Subgraphs
+Normal rank
@@ Property / cites work @@
+Edge-disjoint paths in Planar graphs with constant congestion
+Normal rank
@@ Property / cites work @@
+A note on approximating graph genus
@@ Property / cites work: A note on approximating graph genus / rank @@
+Normal rank
@@ Property / cites work @@
+A tighter insertion-based approximation of the crossing number
+Normal rank
@@ Property / cites work @@
+An algorithm for the graph crossing number problem
+Normal rank
@@ Property / cites work @@
+Q5365099
@@ Property / cites work: Q5365099 / rank @@
+Normal rank
@@ Property / cites work @@
+Subexponential parameterized algorithms on bounded-genus graphs and             <i>H</i>             -minor-free graphs
+Normal rank
@@ Property / cites work @@
+Grid minors in damaged grids
@@ Property / cites work: Grid minors in damaged grids / rank @@
+Normal rank
@@ Property / cites work @@
+Holiest minimum-cost paths and flows in surface graphs
+Normal rank
@@ Property / cites work @@
+Optimally cutting a surface into a disk
@@ Property / cites work: Optimally cutting a surface into a disk / rank @@
+Normal rank
@@ Property / cites work @@
+A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs
+Normal rank
@@ Property / cites work @@
+Computing the shortest essential cycle
@@ Property / cites work: Computing the shortest essential cycle / rank @@
+Normal rank
@@ Property / cites work @@
+Q5708499
@@ Property / cites work: Q5708499 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of the approximation of nonplanarity parameters for cubic graphs
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for Minimum Weight Vertex Separators
+Normal rank
@@ Property / cites work @@
+Computing the orientable genus of projective graphs
+Normal rank
@@ Property / cites work @@
+Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
+Normal rank
@@ Property / cites work @@
+Q5365094
@@ Property / cites work: Q5365094 / rank @@
+Normal rank
@@ Property / cites work @@
+graphs that are irreducible for the projective plane
+Normal rank
@@ Property / cites work @@
+Computing crossing numbers in quadratic time
@@ Property / cites work: Computing crossing numbers in quadratic time / rank @@
+Normal rank
@@ Property / cites work @@
+Q2732568
@@ Property / cites work: Q2732568 / rank @@
+Normal rank
@@ Property / cites work @@
+Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
+Normal rank
@@ Property / cites work @@
+Efficient Planarity Testing
@@ Property / cites work: Efficient Planarity Testing / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549636
@@ Property / cites work: Q3549636 / rank @@
+Normal rank
@@ Property / cites work @@
+Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
+Normal rank
@@ Property / cites work @@
+A Pseudo-approximation for the Genus of Hamiltonian Graphs
+Normal rank
@@ Property / cites work @@
+Combinatorial Local Planarity and the Width of Graph Embeddings
+Normal rank
@@ Property / cites work @@
+A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
+Normal rank
@@ Property / cites work @@
+Face covers and the genus problem for apex graphs
@@ Property / cites work: Face covers and the genus problem for apex graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q2726740
@@ Property / cites work: Q2726740 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimal embeddings in the projective plane
@@ Property / cites work: Minimal embeddings in the projective plane / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. V. Excluding a planar graph
@@ Property / cites work: Graph minors. V. Excluding a planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. VIII: A Kuratowski theorem for general surfaces
+Normal rank
@@ Property / cites work @@
+Graph minors. XVI: Excluding a non-planar graph
@@ Property / cites work: Graph minors. XVI: Excluding a non-planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Quickly excluding a planar graph
@@ Property / cites work: Quickly excluding a planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Call routing and the ratcatcher
@@ Property / cites work: Call routing and the ratcatcher / rank @@
+Normal rank
@@ Property / cites work @@
+The graph genus problem is NP-complete
@@ Property / cites work: The graph genus problem is NP-complete / rank @@
+Normal rank
@@ Property / cites work @@
+Embeddings of graphs with no short noncontractible cycles
+Normal rank
@@ Property / cites work @@
+Triangulating a surface with a prescribed graph
@@ Property / cites work: Triangulating a surface with a prescribed graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q2724086
@@ Property / cites work: Q2724086 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2886408974
@@ Property / OpenAlex ID: W2886408974 / rank @@
+Normal rank