The maximum linear arrangement problem for trees under projectivity and planarity

DOI10.1016/j.ipl.2023.106400zbMath1529.68189arXiv2206.06924MaRDI QIDQ6072193

Lluís Alemany-Puig, Ramon Ferrer-i-Cancho, Juan Luis Esteban

Publication date: 12 October 2023

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

Full work available at URL: https://arxiv.org/abs/2206.06924

zbMATH Keywords

planaritygraph algorithmsprojectivitylinear arrangementsmaximum linear arrangement problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On optimal linear arrangements of trees
• Optimal one-page tree embeddings in linear time
• The book thickness of a graph
• Some simplified NP-complete graph problems
• A dynamic survey of graph labeling
• Approximation algorithms for maximum linear arrangement
• Minimum projective linearizations of trees in linear time
• The number of caterpillars
• Obnoxious Facility Location on Graphs
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• Optimal numberings and isoperimetric problems on graphs
• Trees with Hamiltonian square
• Optimal Assignments of Numbers to Vertices
• Bounds of the sum of edge lengths in linear arrangements of trees