Balanced vertex-orderings of graphs

DOI10.1016/j.dam.2004.12.001zbMath1060.05088OpenAlexW2139924054MaRDI QIDQ1775059

David R. Wood, Yashar Ganjali, Mohammad Taghi Hajiaghayi, Timothy M. Chan, Therese C. Biedl

Publication date: 4 May 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.12.001

zbMATH Keywords

Graph drawingGraph algorithmBalancedVertex-ordering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

Optimal three-dimensional orthogonal graph drawing in the general position model. ⋮ Brushing with additional cleaning restrictions ⋮ On the Most Imbalanced Orientation of a Graph ⋮ The referenced vertex ordering problem: theory, applications, and solution methods ⋮ On the brush number of the Cartesian product of tree with path or cycle ⋮ Algorithmic Applications of Tree-Cut Width ⋮ \textsc{polish} -- Let us play the cleaning game ⋮ Good acyclic orientations of 4‐regular 4‐connected graphs ⋮ Characterization of the imbalance problem on complete bipartite graphs ⋮ Fast edge searching and fast searching on graphs ⋮ Imbalance is fixed parameter tractable ⋮ Three-fast-searchable graphs ⋮ Bounded degree acyclic decompositions of digraphs. ⋮ Cleaning with brooms ⋮ Cleaning random \(d\)-regular graphs with brooms ⋮ The minimum feasible tileset problem ⋮ Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree ⋮ Balanced vertex-orderings of graphs ⋮ Clean the graph before you draw it! ⋮ On the most imbalanced orientation of a graph ⋮ Degree-constrained orientations of embedded graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Imbalance parameterized by twin cover revisited ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Density decompositions of networks ⋮ Algorithmic Applications of Tree-Cut Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast and effective heuristic for the feedback arc set problem
• How to draw a planar graph on a grid
• Area-efficient static and incremental graph drawings
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• st-ordering the vertices of biconnected graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Computing an st-numbering
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• Algorithms for area-efficient orthogonal drawing
• A better heuristic for orthogonal graph drawings
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Time bounds for selection
• Three-dimensional orthogonal graph drawing algorithms
• Balanced vertex-orderings of graphs
• Bipolar orientations revisited
• Optimal three-dimensional orthogonal graph drawing in the general position model.
• Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout
• Drawing planar graphs using the canonical ordering
• THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• On the complexity of bicoloring clique hypergraphs of graphs
• The complexity of satisfiability problems

This page was built for publication: Balanced vertex-orderings of graphs