A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs

DOI10.1007/S00453-008-9275-YMaRDI QIDQ5961977zbMATH OpenOpenAlexFDO

Authors Seok-Hee Hong, Hiroshi Nagamochi

Publication date 16 September 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9275-y

zbMATH Keywords

angle-constrained graph drawingconvex drawinggeometric automorphismgraph drawinginternally triconnected plane graphsplanar graphssymmetric drawingsymmetrytriconnected planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 2119683
• A linear time algorithm for constructing maximally symmetric straight line drawings of triconnected planar graphs
• Drawing planar graphs symmetrically. III: Oneconnected planar graphs
• Drawing planar graphs symmetrically. II: Biconnected planar graphs
• Convex Drawings of Internally Triconnected Plane Graphs on O(n 2) Grids

Cites work

• A linear time algorithm for constructing maximally symmetric straight line drawings of triconnected planar graphs
• A reductive technique for enumerating non-isomorphic planar maps
• Algorithms and Computation
• Convex drawings of graphs with non-convex boundary constraints
• CONVEX DRAWINGS OF PLANE GRAPHS OF MINIMUM OUTER APICES
• CONVEX GRID DRAWINGS OF FOUR-CONNECTED PLANE GRAPHS
• Convex Grid Drawings of Plane Graphs with Rectangular Contours
• Convex Representations of Graphs
• Drawing planar graphs symmetrically. II: Biconnected planar graphs
• Drawing planar graphs symmetrically. III: Oneconnected planar graphs
• Drawing series parallel digraphs symmetrically
• Fast detection and display of symmetry in outerplanar graphs
• Generalized Nested Dissection
• Graph Drawing
• Graph theory with applications
• How to Draw a Graph
• scientific article; zbMATH DE number 2084276 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3882450 (Why is no real title available?)
• scientific article; zbMATH DE number 3885930 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 1974110 (Why is no real title available?)
• scientific article; zbMATH DE number 4114655 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Some NP-Complete Problems Similar to Graph Isomorphism
• Spring algorithms and symmetry
• Strictly convex drawings of planar graphs
• Time bounded random access machines

Cited in

(7)

• A force-directed algorithm for drawing directed graphs symmetrically
• A linear time algorithm for constructing maximally symmetric straight line drawings of triconnected planar graphs
• Optimal angular resolution for face-symmetric drawings
• Convex Drawings of Internally Triconnected Plane Graphs on O(n 2) Grids
• scientific article; zbMATH DE number 2104042 (Why is no real title available?)
• scientific article; zbMATH DE number 2119683 (Why is no real title available?)
• Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra

Describes a project that uses

Uses Software

• PIGALE

This page was built for publication: A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs

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