On the page number of upward planar directed acyclic graphs

DOI10.1007/978-3-642-25878-7_37MaRDI QIDQ3223971zbMATH OpenOpenAlexFDO

Authors Fabrizio Frati, Radoslav Fulek, Andres J. Ruiz-Vargas

Publication date 9 March 2012

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25878-7_37

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• On the page number of upward planar directed acyclic graphs
• scientific article; zbMATH DE number 431511
• scientific article; zbMATH DE number 432821
• Ordered sets, pagenumbers and planarity
• On the number of upward planar orientations of maximal planar graphs

Cites work

• Algorithms for plane representations of acyclic digraphs
• Book embeddability of series-parallel digraphs
• Coloring circle graphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Covering and coloring polygon-circle graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Genus g Graphs Have Pagenumber O(√g)
• Graphs with E Edges Have Pagenumber O(√E)
• On the pagenumber of complete bipartite graphs
• Sorting Using Networks of Queues and Stacks
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Stack and Queue Layouts of Posets
• The pagenumber of \(k\)-trees is \(O(k)\)
• The pagenumber of genus g graphs is O( g )
• Thickness and coarseness of graphs

Cited in

(7)

• Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs
• On the page number of upward planar directed acyclic graphs
• A Sublinear Bound on the Page Number of Upward Planar Graphs
• The pagenumber of toroidal graphs is at most seven
• On the page number of triple-loop networks with even cardinality.
• Upward partitioned book embeddings
• Recognizing DAGs with page-number 2 is NP-complete

This page was built for publication: On the page number of upward planar directed acyclic graphs

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