Geometric representation of graphs in low dimension using axis parallel boxes

DOI10.1007/s00453-008-9163-5zbMath1216.05089WikidataQ29039815 ScholiaQ29039815MaRDI QIDQ848956

L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9163-5

zbMATH Keywords

randomized algorithm; random graph; derandomization; intersection graphs; boxicity

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

05C62: Graph representations (geometric and intersection representations, etc.)