Clean the graph before you draw it!

DOI10.1016/j.ipl.2009.01.003zbMath1209.68369OpenAlexW2044593143MaRDI QIDQ987793

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

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

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Game brush number ⋮ Brushing with additional cleaning restrictions ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ \textsc{polish} -- Let us play the cleaning game ⋮ Imbalance is fixed parameter tractable ⋮ Brushing without capacity restrictions ⋮ Elimination schemes and lattices ⋮ Cleaning with brooms ⋮ Cleaning random \(d\)-regular graphs with brooms ⋮ Brushing number and zero-forcing number of graphs and their line graphs ⋮ Parallel cleaning of a network with brushes ⋮ On the Complexity Landscape of the Domination Chain ⋮ Algorithmic Applications of Tree-Cut Width

Cites Work

• Unnamed Item
• Unnamed Item
• Cleaning a network with brushes
• Parallel cleaning of a network with brushes
• Algorithms for area-efficient orthogonal drawing
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Balanced vertex-orderings of graphs
• 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
• Cleaning Regular Graphs with Brushes
• Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm

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