AMENDED AND RESTATED AGREEMENT REGARDING REGISTRATION OF SHARES

Exhibit 4.2

AMENDED AND RESTATED
AGREEMENT REGARDING REGISTRATION OF SHARES

This AMENDED AND RESTATED AGREEMENT REGARDING REGISTRATION OF SHARES (“Agreement”) is made as of August 4, 2004 by and between NAVTEQ Corporation (“Company”) and NavPart I B.V. (“Stockholder”).

WHEREAS, on April 20, 2004, the Company has filed a registration statement on Form S-1 (as amended, “Registration Statement”) with the Securities and Exchange Commission under the Securities Act of 1933, as amended (“Act”), to register the offer and sale of certain shares of the Company’s common stock, $0.001 par value, held by Philips Consumer Electronic Services B.V. (“Philips”) pursuant to a firm commitment underwritten public offering (“Offering”); and

WHEREAS, the Stockholder has requested that the Company register the offer and sale under the Act certain shares of the Company’s common stock it holds (“Stockholder Shares”) by including such shares in the Registration Statement; and

WHEREAS, the Company has indicated its willingness to include such Stockholder Shares in the Registration Statement, and on May 17, 2004, the Company and Stockholder entered into an Agreement Regarding Registration of Shares (“Original Agreement”); and

WHEREAS, since the date of the Original Agreement certain events have occurred that all parties agree require an amendment of the terms and conditions specified in the Original Agreement;.

NOW, THEREFORE, in consideration of the mutual promises and covenants contained herein, the parties agree as follows:

1.                                       Agreement to Register Shares.  Subject to the conditions set forth herein, the Company agrees to use its commercially reasonable efforts to register the Stockholder Shares by including such shares in the Registration Statement.  The number of Stockholder Shares to be registered will be determined through consultation with Credit Suisse First Boston LLC and Merrill Lynch & Co., the Underwriters of the Offering.  Such number of shares may be increased or decreased at any time prior to the completion of the Offering in the sole discretion of the Underwriters.

2.                                       Conditions to Company’s Obligation.  In addition to the condition set forth in Section 5 below, the obligations of the Company to include the Stockholder Shares in the Registration Statement are expressly subject to the following conditions:

(a)                                  the Stockholder shall become a party to the Underwriting Agreement between the Company, the Underwriters, Philips and the Stockholder;

(b)                                 the Stockholder cooperates with the Company and the Underwriters as requested by the Company and/or Underwriters in connection with the Registration

Statement and the Offering, including, without limitation, providing such information as is requested by them for inclusion in the Registration Statement and executing such agreements, acknowledgments and certificates as are customary in transactions of this type;

(c)                                  Philips consents to the inclusion of the Stockholder Shares in the Registration Statement; and

(d)                                 the Registration Statement is not withdrawn and/or the Offering is not completed for any reason.

3.                                       Fees and Expenses.  The Company shall be responsible for the Securities and Exchange Commission, National Association of Securities Dealers, Inc., New York Stock Exchange and “blue sky” law registration, qualification and compliance fees and expenses in connection with the registration of the Stockholder Shares.  The Selling Stockholder shall be responsible for all underwriting discounts, selling commissions and transfer taxes, if any, applicable to the sale of the Stockholder Shares., and the fees and expenses of its counsel.

4.                                       No Other Registration Rights.  The Stockholder acknowledges and agrees that the Company’s agreement to register the Stockholder Shares pursuant to this Agreement does not create any further right of Stockholder to have any of its shares registered in any subsequent registration of the offer and sale of Company securities under the Act (whether in an offering by the Company or for the account of any Company securityholder).  The Stockholder further acknowledges and agrees that nothing in this Agreement is intended to make the Stockholder a party to or confer upon such Stockholder any rights set forth in that certain Registration Rights Agreement dated as of March 29, 2001 by and between the Company and Philips.

5.                                       Agreement of Underwriters.  The obligations of the Company and the rights of the Stockholder under this Agreement are expressly conditioned on the consent and agreement of the Underwriters to include the Stockholder Shares in the Offering.  In the event that the Underwriters determine, in their sole discretion, not to include the Stockholder Shares in the Offering, the Company’s obligations under this Agreement shall cease and be of no further force or effect.

6.                                       Reasonable Investigation.  In connection with the preparation and filing of the Registration Statement and the completion of the Offering, the Company will provide the Stockholder reasonable and customary access to the Company’s books and records and such opportunities to discuss the business of the Company with its officers as shall be reasonably necessary to conduct a reasonable investigation within the meaning of the Act.

7.                                       Representations, Warranties and Agreements of Stockholder.  This Agreement has been duly authorized, executed and delivered by or on behalf of Stockholder.  Stockholder has, and at the closing of the Offering will have, valid title to the Stockholder Shares free and clear of all security interests, claims, liens, equities or other encumbrances and the

2

legal right and power, and all authorization and approval required by law, to enter into this Agreement and to sell, transfer and deliver the Stockholder Shares.

8.                                       Indemnification and Contribution.

(a)                                  Indemnification by the Company. The Company shall indemnify and hold harmless Stockholder, and its officers and directors and each Person who controls Stockholder within the meaning of Section 15 of the Act or Section 20 of the Securities Exchange Act of 1934 (the “Exchange Act”) (each such person being sometimes referred to as an “Indemnified Person”) against any losses, claims, damages or liabilities, joint or several, to which such Indemnified Person may become subject under the Act or otherwise, insofar as such losses, claims, damages or liabilities (or actions in respect thereof) arise out of or are based upon an untrue statement or alleged untrue statement of a material fact contained in the Registration Statement, or any Prospectus contained therein, or any amendment or supplement thereto, or arise out of or are based upon the omission or alleged omission to state therein a material fact required to be stated therein or necessary to make the statements therein not misleading, and the Company hereby agrees to reimburse such Indemnified Person for any legal or other expenses reasonably incurred by them in connection with investigating or defending any such action or claim as such expenses are incurred; provided, however, that the Company shall not be liable to any such Indemnified Person in any such case to the extent that any such loss, claim, damage or liability arises out of or is based upon an untrue statement or alleged untrue statement or omission or alleged omission made in the Registration Statement or Prospectus, or amendment or supplement, in reliance upon and in conformity with written information furnished to the Company by Stockholder expressly for use therein.  For purposes of this Section 8, the term “Person” means any individual, partnership, corporation or similar entity, trust or unincorporated organization, and the term “Prospectus” means the prospectus included in the Registration Statement, including any preliminary prospectus, and any supplement thereto.

(b)                                 Indemnification by Stockholder.  Stockholder agrees to (i) indemnify and hold harmless the Company, and its directors and officers who sign the Registration Statement and each Person, if any, who controls the Company within the meaning of either Section 15 of the Act or Section 20 of the Exchange Act, against any losses, claims, damages or liabilities to which the Company or such other persons may become subject, under the Act or otherwise, insofar as such losses, claims, damages or liabilities (or actions in respect thereof) arise out of or are based upon an untrue statement or alleged untrue statement of a material fact contained in the Registration Statement or Prospectus, or any amendment or supplement, or arise out of or are based upon the omission or alleged omission to state therein a material fact required to be stated therein or necessary to make the statements therein not misleading, in each case to the extent, but only to the extent, that such untrue statement or alleged untrue statement or omission or alleged omission was made in reliance upon and in conformity with written information furnished to the Company by Stockholder expressly for use therein, and (ii) reimburse the Company for any legal or other expenses reasonably incurred by the Company in connection with investigating or defending any such action or claim as such expenses are incurred.

3

(c)                                  Notices of Claims, Etc.  Promptly after receipt by an indemnified party under subsection (a) or (b) above of notice of the commencement of any action, such indemnified party shall, if a claim in respect thereof is to be made against an indemnifying party under this Section 8, notify such indemnifying party in writing of the commencement thereof; but the omission so to notify the indemnifying party shall not relieve it from any liability which it may have to any indemnified party otherwise than under this Section 8. In case any such action shall be brought against any indemnified party and it shall notify an indemnifying party of the commencement thereof, such indemnifying party shall be entitled to participate therein and, to the extent that it shall wish, jointly with any other indemnifying party similarly notified, to assume the defense thereof, with counsel reasonably satisfactory to such indemnified party (who shall not, except with the consent of the indemnified party, be counsel to the indemnifying party), and, after notice from the indemnifying party to such indemnified party of its election so to assume the defense thereof, such indemnifying party shall not be liable to such indemnified party under this Section 8 for any legal expenses of other counsel or any other expenses, in each case subsequently incurred by such indemnified party, in connection with the defense thereof other than reasonable costs of investigation. No indemnifying party shall, without the written consent of the indemnified party, effect the settlement or compromise of, or consent to the entry of any judgment with respect to, any pending or threatened action or claim in respect of which indemnification or contribution may be sought hereunder (whether or not the indemnified party is an actual or potential party to such action or claim) unless such settlement, compromise or judgment (i) includes an unconditional release of the indemnified party from all liability arising out of such action or claim and (ii) does not include a statement as to, or an admission of, fault, culpability or a failure to act, by or on behalf of any indemnified party.

(d)                                 Contribution. If the indemnification provided for in this Section 8 is unavailable to or insufficient to hold harmless an indemnified party under subsection (a) or (b) above in respect of any losses, claims, damages or liabilities (or actions in respect thereof) referred to therein, then each indemnifying party shall contribute to the amount paid or payable by such indemnified party as a result of such losses, claims, damages or liabilities (or actions in respect thereof) in such proportion as is appropriate to reflect the relative fault of the indemnifying party and the indemnified party in connection with the statements or omissions which resulted in such losses, claims, damages or liabilities (or actions in respect thereof), as well as any other relevant equitable considerations. The relative fault of such indemnifying party and indemnified party shall be determined by reference to, among other things, whether the untrue or alleged untrue statement of a material fact or omission or alleged omission to state a material fact relates to information supplied by such indemnifying party or by such indemnified party, and the parties’ relative intent, knowledge, access to information and opportunity to correct or prevent such statement or omission. The amount paid or payable by an indemnified party as a result of the losses, claims, damages or liabilities (or actions in respect thereof) referred to above shall be deemed to include any legal or other fees or expenses reasonably incurred by such indemnified party in connection with investigating or defending any such action or claim to the extent such fees or expenses were incurred prior to an indemnifying party’s election to

4

assume the defense of such action or claim. No person guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of the Act) shall be entitled to contribution from any person who was not guilty of such fraudulent misrepresentation.

(e)                                  Limitation.  Notwithstanding any other provision of this Section 8, in no event will Stockholder be required to undertake liability to any Person under this Section 8 for any amounts in excess of the dollar amount of the proceeds to be received by Stockholder from the sale of Stockholder Shares in the Offering (after deducting any fees, discounts and commissions applicable thereto).

(f)                                    Non-Exclusive Remedy. The obligations of the Company under this Section 8 shall be in addition to any liability which the Company may otherwise have to any Indemnified Person and the obligations of any Indemnified Person under this Section 8 shall be in addition to any liability which such Indemnified Person may otherwise have to the Company.  The remedies provided in this Section 8 are not exclusive and shall not limit any rights or remedies which may otherwise be available to an indemnified party at law or in equity.

9.                                       Non-Transferability.  The rights and obligations of the Stockholder under this Agreement may not be transferred or assigned without the written agreement of the Company.

10.                                 Governing Law.  This Agreement and the rights and obligations of the parties hereto shall be governed by and construed in accordance with the laws of the state of Delaware, but not including the choice of law rules thereof.

11.                                 Entire Agreement.  This Agreement constitutes the full and entire understanding and agreement of the parties with regard to the subject matters described herein and supersedes and any and all prior agreements and understandings between the parties with regard to the subject matters described herein.  This Agreement may be amended or modified only by written agreement of the parties.

12.                                 Execution in Counterparts.  This Agreement may be executed in any number of counterparts, each of which shall be an original, but all of which together shall constitute one instrument.

[REMAINDER OF PAGE INTENTIONALLY BLANK - SIGNATURE PAGE FOLLOWS]

5

[signature page - Agreement Regarding Registration Of Shares]

IN WITNESS WHEREOF,  the parties have executed this Agreement as of the date first set forth above.

6