Computational topology of graphs on surfaces
Computational topology of graphs on surfaces
Computational topology is an area that revisits topological problems from an algorithmic point of view, and develops topological tools for improved algorithms. We survey results in computational topology that are concerned with graphs drawn on surfaces. Typical questions include representing surfaces and graphs embedded on them computationally, deciding whether a graph embeds on a surface, solving computational problems related to homotopy, optimizing curves and graphs on surfaces, and solving standard graph algorithm problems more efficiently in the case of surface-embedded graphs.
To appear in the Handbook of Discrete and Computational Geometry, 3rd edition. Minor changes compared to previous version
Computational Geometry (cs.CG), FOS: Computer and information sciences, F.2.2; G.2.2; I.3.5, Discrete Mathematics (cs.DM), I.3.5, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-AT] Mathematics [math]/Algebraic Topology [math.AT], G.2.2, 68U05, 05C10, 57M15, 68R10, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Computer Science - Data Structures and Algorithms, FOS: Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics, Algebraic Topology (math.AT), Data Structures and Algorithms (cs.DS), Mathematics - Algebraic Topology, Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, F.2.2; G.2.2; I.3.5, Discrete Mathematics (cs.DM), I.3.5, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-AT] Mathematics [math]/Algebraic Topology [math.AT], G.2.2, 68U05, 05C10, 57M15, 68R10, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Computer Science - Data Structures and Algorithms, FOS: Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics, Algebraic Topology (math.AT), Data Structures and Algorithms (cs.DS), Mathematics - Algebraic Topology, Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!