On the complexity of planar Boolean circuits

DOI10.1007/BF01277954zbMath0816.68069OpenAlexW1707277566MaRDI QIDQ1842774

György Turán

Publication date: 19 July 1995

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01277954

zbMATH Keywords

planar graphscircuit complexityplanar circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Related Items (5)

Communication Complexity and Lower Bounds on Multilective Computations ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Succinct certification of monotone circuits ⋮ Succinct monotone circuit certification: planarity and parameterized complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• Lower bounds to the complexity of symmetric Boolean functions
• The performance of multilective VLSI algorithms
• Multiple cuts, input repetition, and VLSI complexity
• The planar realization of Boolean functions
• Lower bounds for synchronous circuits and planar circuits
• Meanders and their applications in lower bounds arguments
• Explicit constructions of linear-sized superconcentrators
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Two tapes versus one for off-line Turing machines
• A Separator Theorem for Planar Graphs
• Planar Crossovers
• Applications of a Planar Separator Theorem
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions

This page was built for publication: On the complexity of planar Boolean circuits