Clean the graph before you draw it!

DOI10.1016/J.IPL.2009.01.003MaRDI QIDQ987793zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Margaret-Ellen Messinger, R. J. Nowakowski, Paweł Prałat

Publication date 16 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.01.003

zbMATH Keywords

computational complexitygraph algorithmsbrush numberbalanced vertex-ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Brushing with additional cleaning restrictions
• Brushing without capacity restrictions
• Computing and Combinatorics
• On the complexity of the balanced vertex ordering problem
• Balanced vertex-orderings of graphs

Cites work

• Algorithms for area-efficient orthogonal drawing
• Balanced vertex-orderings of graphs
• Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm
• Cleaning a network with brushes
• Cleaning random graphs with brushes
• Cleaning regular graphs with brushes
• Drawing planar graphs using the canonical ordering
• Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout
• On the complexity of the balanced vertex ordering problem
• Optimal three-dimensional orthogonal graph drawing in the general position model.
• Parallel cleaning of a network with brushes
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems

Cited in

(16)

• Computing and Combinatorics
• Brushing number and zero-forcing number of graphs and their line graphs
• Algorithmic applications of tree-cut width
• Game brush number
• Brushing with additional cleaning restrictions
• Cleaning with brooms
• Cleaning random \(d\)-regular graphs with brooms
• On the complexity landscape of the domination chain
• Parallel cleaning of a network with brushes
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• \textsc{polish} -- Let us play the cleaning game
• On the complexity of the balanced vertex ordering problem
• To Fix Those Plots, Use Limits!
• Brushing without capacity restrictions
• Imbalance is fixed parameter tractable
• Elimination schemes and lattices

This page was built for publication: Clean the graph before you draw it!

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