Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Wikipedia says graph theory is used in computer chip design.

... travel, biology, computer chip design, and many other fields. ...

Is there a good reference for that? I can imagine optimal way to draw cpu to chip is to draw shortest hamiltonian cycle in it.

share|improve this question
add comment

4 Answers 4

I'm not sure what would constitute a good reference given the breadth of applications of graph theory in integrated circuit design.

You could glance at the floorplanning, placement and routing chapters of Smith's "Application specific integrated circuits" to get a feel for what is involved. It is an old book (1997) but gives a decent, fairly concise overview.

However, the term 'optimal' is hard to characterize in terms of cpu design, there are many conflicting objectives that need to be addressed. The old adage was "power, speed, area - pick two". Design (in the broad sense) has become considerably more complicated since those relatively simple days.

share|improve this answer
    
Should "breath" be "breadth"? –  Code-Guru Mar 3 '13 at 0:13
    
Indeed it should, thanks... –  copper.hat Mar 3 '13 at 2:54
add comment

I don't know about a reference. However, the intuition is that an electrical circuit in a computer chip design is etched into a flat surface. This implies that the graph model of this circuit must be a planar graph. So the theory behind planar graphs is very important in designing such circuits.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.